package cyc2018.贪心思想;

import java.util.LinkedList;
import java.util.List;

/**
 * 划分字母区间
 *
 * 设立一个 lastIndex 数组存放每个字母最后一次出现的位置，
 * 然后从前向后找，如果一个区间里面某个字符的最后一个位置比这个区间的终点还要靠后，
 * 那么区间的终点=这个字符的最后一次出现的位置，时间O(N),贪心算法
 */
public class Test763 {

    public static List<Integer> partitionLabels(String S) {
        int lastindex[] = new int[26];
        int start = 0;
        int len = S.length();
        int end = 0;
        int i = 0;
        char ch[] = S.toCharArray();

        lastIndex(ch, lastindex);

        List<Integer> ans = new LinkedList<>();
        while (start < len) {
            char startchar = ch[start];
            // 找到 s 中当前字母最后一次出现的位置
            end = lastindex[startchar - 'a'];
            i = start;

            // 【核心】从前向后找，如果一个区间里面某个字符的最后一个位置比这个区间的终点还要靠后，
            // 那么区间的终点=这个字符的最后一次出现的位置，
            while (i <= end) {
                if (lastindex[ch[i] - 'a'] > end) {
                    end = lastindex[ch[i] - 'a'];
                }
                i++;
            }
            ans.add(end - start + 1);
            start = end + 1;
        }
        return ans;
    }

    public static void lastIndex(char ch[], int index[]) {
        int i;
        int len = ch.length;
        for (i = 0; i < 26; i++) {
            index[i] = -1;
        }
        // 找出每个字母最后一次出现的位置
        for (i = len - 1; i >= 0; i--) {
            int patition = ch[i] - 'a';
            if (index[patition] == -1)
                index[patition] = i;
        }
    }

    public static void main(String[] args) {
        String s = "ababcbacadefegdehijhklij";
        List<Integer> list = partitionLabels(s);
        list.forEach((e) -> System.out.println(e));
    }
}
